1. Field of the Invention
This invention relates to multiplication circuitry for digital computers and more specifically for multipliers in digital computers that employ table lookup techniques.
2. Description of the Prior Art
Multiplication in digital processors has traditionally been accomplished by two different methods. The first method requires that the digital processor execute an algorithm that takes the multiplicand and multiplier and combines them together by a series of additions and shift operations. Such a multiplication technique is described in Production to Digital Computer Design, by Herbert S. Sobel, published by Addison Westley Publishing Co., 1970. This method will provide products for hexidecimal numbers and with a further procedure provide products for binary coded decimal numbers.
The second method of multiplication is the use of the lookup table. That is, the multiplier and multiplicand are used as inputs to a table to lookup the result (i.e., the product of the specific multiplier and multiplicand). This method has the advantage of speed over the first method of executing an algorithm. However, the use of a lookup table also requires the storage of the multiplication table in the computer. If the multiplication table is stored in ROM (Read-Only Memory), the area required by this table may be quite large. It is an object of the present invention to provide a multiplication table with reduced table memory area requirements.
Recently, reduction techniques have been used to reduce the size of control logic and microcode storage memory in 16 bit microprocessors. One technique involves compression of the number of bits used in the read-only memory containing the microcode. In addressing microcode reduction, the standard approach has been to break the control word (i. e., the portion of the instruction word that specifies the operation of the microprocessor) into fields such as a jump field and a register control field where each field contains partially encoded control information together with the instruction register information to produce the control signals from the control ROM. An additional technique uses this partially encoded approach, plus it uses state redundancy with a two level control ROM structure to reduce the total ROM requirements. This two level approach generates a set of common control words (as is also the case for microsubroutine) for a horizontal store that is addressed by a second narrow control word (or vertical store). The primary control signals are those signals that directly control the machine (such as LATCH, LOAD SIGNALS, ALU (Arithmetic logic unit) CONTROL SIGNALS AND MICROJUMP ADDRESS), as opposed to secondary control signals that must be combined or decoded to form primary control signals. Assuming that the hardware to be controlled is relatively fixed, the number of primary control signals is fixed, and therefore the final result of any control structure is to generate this relatively fixed number of primary signals. In the past, the compressed control ROM technique has been used to reduce the total number of bits of information required in the control ROM to produce the fixed number of control signals. This technique and other techniques that will be discussed are applied to reduce and alter the traditional architecture of the multiplication table in a microprocessor or microcomputer.